package com.tree.treeBaseOnlink;

public class TreeBaseOnLink {

	private class SonNode{
		private SonNode nextSonNode;
		private int index;
		public SonNode(SonNode nextSonNode, int index) {
			super();
			this.nextSonNode = nextSonNode;
			this.index = index;
		}
		
		public SonNode getNextSonNode() {
			return nextSonNode;
		}

		public void setNextSonNode(SonNode nextSonNode) {
			this.nextSonNode = nextSonNode;
		}

		public int getIndex() {
			return index;
		}
		public void setIndex(int index) {
			this.index = index;
		}
	}
	
	private class Node{
		private SonNode firstSonNode;
		private String data;
		public Node(String data) {
			super();
			this.data = data;
			
		}
		public Node() {
		}
		public SonNode getFirstSonNode() {
			return firstSonNode;
		}
		public void setFirstSonNode(SonNode firstSonNode) {
			this.firstSonNode = firstSonNode;
		}
		public String getData() {
			return data;
		}
		public void setData(String data) {
			this.data = data;
		}
		@Override
		public String toString() {
			return "Node [firstSonNode=" + firstSonNode + ", data=" + data
					+ "]";
		}
		
		
	}
	
	private Node[] treeNodes;
	private int nodeCount;
	private int DEFAULT_COUNT=20;
	private int treeSize;
	public TreeBaseOnLink(String root,int treeSize) {
		super();
		this.treeSize = treeSize;
		treeNodes=new Node[treeSize];
		treeNodes[0]=new Node(root);
		nodeCount++;
	}
	
	public boolean addNode(String parent,String data){
		Node node=getNode(parent);
		Node node2=new Node(data);
		treeNodes[nodeCount]=node2;
		addSonNode(node, new SonNode(null, nodeCount++));
		return true;
	}
	
	private boolean addSonNode(Node node ,SonNode sonNode){
		SonNode sonNodeFirst=node.getFirstSonNode();
		if(null==node.getFirstSonNode()){
			node.setFirstSonNode(sonNode);
		}else {
			SonNode next=sonNodeFirst;
			while(next.nextSonNode!=null){
				next=next.nextSonNode;
			}
			next.nextSonNode=sonNode;
		}
		return true;
	}
	
	public Node getNode(String data){
		for (int i = 0; i < nodeCount; i++) {
			if(treeNodes[i].getData().equals(data))
				return treeNodes[i];
		}
		return null;
	}
	
	private int getNodeIndex(String data){
		for (int i = 0; i < nodeCount; i++) {
			if(treeNodes[i].getData().equals(data)){
				return i;
			}
		}
		return 0;
	}
	
	public Node getParent(String data){
		int index;
		if((index=getNodeIndex(data))==0)
			return null;
		for (int i = 0; i < nodeCount; i++) {
			if(null!=treeNodes[i].getFirstSonNode()){
				SonNode sonNode=treeNodes[i].getFirstSonNode();
				if(sonNode.getIndex()==index)
					return treeNodes[i];
				while(null!=sonNode.nextSonNode){
					sonNode=sonNode.nextSonNode;
					if(sonNode.index==index)
						return treeNodes[i];
				}
			}
		}
		return null;
	}
	
	public Node[] getChildren(String data){
		SonNode sonNode=null;
		for (int i = 0; i < nodeCount; i++) {
			if(treeNodes[i].getData().equals(data)){
				sonNode=treeNodes[i].getFirstSonNode();
			}
		}
		if(sonNode==null)
			return null;
		Node[] childrenNodes=new Node[treeSize];
		childrenNodes[0]=treeNodes[sonNode.getIndex()];
		int count=1;
		while(null!=sonNode.nextSonNode){
			sonNode=sonNode.nextSonNode;
			childrenNodes[count++]=treeNodes[sonNode.getIndex()];
		}
		return childrenNodes;
	}
	
	public int depth(){
		if(nodeCount<1){
			return 0;
		}else {
			return deep(treeNodes[0], 1);
		}
	}
	private int deep(Node node,int deep){
		if(nodeCount<=2&&nodeCount>0)
			return nodeCount==1?1:2;
		int temp=0;
		Node[] childrenNodes=getChildren(node.getData());
		if(childrenNodes!=null){
			for (Node node2 : childrenNodes) {
				if(node2!=null)
				{
					int deepChild=deep(node2, deep+1);
					if(deepChild>temp){
						temp=deepChild;
					}
				}
			}
			return temp;
		}else {
			return deep;
		}
	}
	
	public static void main(String[] args) {
		TreeBaseOnLink tree=new TreeBaseOnLink("A", 15);
		tree.addNode("A", "B");
		tree.addNode("A", "C");
		tree.addNode("A", "D");
		tree.addNode("B","E");
		tree.addNode("D", "F");
		tree.addNode("D", "G");
		tree.addNode("E", "H");
		tree.addNode("E", "I");
		tree.addNode("E", "J");
		tree.addNode("G", "K");
		tree.addNode("I","L");
		tree.addNode("K", "M");
		tree.addNode("M", "N");
		for (Node node : tree.getChildren("E")) {
			System.out.println(node);
		}
		System.out.println(tree.getParent("B"));
		System.out.println(tree.depth());
		
	}
}
